package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
题型： 回溯 - 排序

https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
https://leetcode.cn/problems/permutations/description/

46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]
 */
class leetcode_46 {
    @Test
    fun test_1() {
        val actual = permute(intArrayOf(1, 2, 3))
        val expect = arrayListOf(
            arrayListOf(1, 2, 3), arrayListOf(1, 3, 2), arrayListOf(2, 1, 3), arrayListOf(2, 3, 1), arrayListOf(3, 1, 2), arrayListOf(3, 2, 1)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = permute(intArrayOf(0, 1))
        val expect = arrayListOf(
            arrayListOf(0, 1), arrayListOf(1, 0)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = permute(intArrayOf(1))
        val expect = arrayListOf(
            arrayListOf(1)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    fun permute(nums: IntArray): List<List<Int>> {
        /*
        回溯法
        1 结果在叶子节点
        2 排列问题
         */
        val path: ArrayList<Int> = ArrayList<Int>()
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        backtracking(nums, path, result, BooleanArray(nums.size))
        return result
    }

    private fun backtracking(nums: IntArray, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>, used: BooleanArray) {
        // 结束条件
        // 收集结果
        if (path.size == nums.size) {
            val t: ArrayList<Int> = ArrayList<Int>()
            t.addAll(path)
            result.add(t)
            return
        }

        for (i in  0 until nums.size) { // [0, end index]
            // 处理节点
            // 树枝去重：已经取过的数字，不能再取了
            if (used[i] == true) {
                continue
            }
            path.add(nums[i])
            used[i] = true

            // 递归
            backtracking(nums, path, result, used)

            // 回溯
            path.removeAt(path.size - 1)
            used[i] = false
        }
    }
}